package algorithm.leetcode;

/**
 * 递归是自顶向下的解决问题，而动态规划则是自底向上的来解决问题，从简单的问题来逐步的交叠出复杂的问题。
 *
 * 动态规划框架
 * dp[0][0][...] = 边界值
 * for(状态1 ：所有状态1的值){
 *     for(状态2 ：所有状态2的值){
 *         for(...){
 *           //状态转移方程
 *           dp[状态1][状态2][...] = 求最值
 *         }
 *     }
 * }
 *
 * @author wuwen
 * @since 2023/12/18
 */
public class NO70_爬楼梯 {
    public static void main(String[] args) {
        System.out.println(new SolutionDP().climbStairs(5));
    }

    /**
     * 递归之所以会超时是因为计算了很多重复的状态
     */
    static class SolutionDP {
        public int climbStairs(int n) {
            if (n <= 3) {
                return n;
            }
            int[] dp = new int[n+1];
            dp[1] = 1;
            dp[2] = 2;
            for (int i = 3; i < n+1; i++) {
                dp[i] = dp[i-1] + dp[i-2];
            }
            return dp[n];
        }
    }
}
